package com.shm.leetcode;

/**
 * 84. 柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *
 *
 *
 *
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 *
 *
 *
 *
 *
 * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
 *
 *
 *
 * 示例:
 *
 * 输入: [2,1,5,6,2,3]
 * 输出: 10
 * @author SHM
 */
public class LargestRectangleArea {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if(n==0){
            return 0;
        }
        int ret = 0;
        for(int i=0;i<n;i++){
            int width = heights[i];
            int area = width;
            for(int k=i-1;k>=0;k--){
                width = Math.min(width,heights[k]);
                area = Math.max(area,(i-k+1)*width);
            }
            ret = Math.max(ret,area);
        }
        return ret;
    }
}
